package leetCode.secondWeek;

import java.util.LinkedList;
import java.util.List;

public class Code_52 {
  public List<List<Integer>> res = new LinkedList<>();

  public int totalNQueens(int n) {
    List<Integer> tmp = new LinkedList<>();
    /** tmp-暂存已添加的节点 **** initial-开始搜索的位置 **** n-纬度 */
    bfs(tmp, n);
    return res.size();
  }

  /**
   * @param tmp
   * @param n
   */
  public void bfs(List<Integer> tmp, int n) {
    if (tmp.size() == n) {
      res.add(new LinkedList<>(tmp));
      return;
    }
    for (int i = 0; i < n; i++) {
      // 如果合法，将节点加入tmp
      if (isLegal(tmp, i, n)) {
        tmp.add(i);
        bfs(tmp, n);
        tmp.remove(tmp.size() - 1);
      }
    }
  }

  public boolean isLegal(List<Integer> former, int insert, int size) {
    // 纵向去重
    if (former.contains(insert)) {
      return false;
    }

    // 斜向去重
    for (int i = former.size() - 1; i >= 0; i--) {
      if (former.get(i) == insert - (former.size() - i)
          | former.get(i) == insert + (former.size() - i)) {
        return false;
      }
    }
    return true;
  }
}
